package com.study.leetcode;

//https://leetcode.cn/problems/recover-binary-search-tree/
public class Solution_99 {
    /**
     * 基本思路：
     * 二叉搜索树的中序遍历是一个有序的序列
     * 在遍历的时候只要可以发现这样的逆序并记录下来最终交换这两个节点的值就可以了
     * 我们对错误的二叉树进行 中序遍历 那我们按顺序访问到的数应该是按顺序排列的
     * 那如果对两个节点交换了顺序  那一定有两个地方是  不满足  前一个元素 < 当前元素 < 后一个元素
     *  如示例2      3  1  4   2：
     *               3  这个节点不满足      1 这个节点不满足
     *              所以我们使用两个全局变量在遍历过程中记录这两个节点 最后对他们进行交换
     */
    TreeNode t1, t2, pre;

    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }

    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        if (pre != null && pre.val > root.val) {
            if (t1 == null) {
                t1 = pre;
            }
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }
}
